week2手寫作業 戴偉璿
第一題:
note:x→∞limk=k,x→∞limx1=0
a.
n→∞limn−13n+1=n→∞lim(1−n1)n→∞lim(3+n1)=13=3
b.
n→∞limn2+1n=n→∞lim(n+n1)n→∞lim1=n1
note:f(n)∈O(g(n))⇔ ∃k>0,∃N,∀n>N,f(n)≤k⋅g(n)
c.
f(n)∈O(2n)⟺f(n)∈O(2n+1)
(1).prooff(n)∈O(2n)⟹f(n)∈O(2n+1)
∵f(n)∈O(2n)
∴∃k≥0,n→∞lim2nf(n)=k
∴n→∞lim2n+1f(n)=n→∞lim2nf(n)⋅21=k⋅21,仍為一常數
∴f(n)∈O(2n+1),成立
(2).prooff(n)∈O(2n)⟸f(n)∈O(2n+1)
∵f(n)∈O(2n+1)
∴∃k≥0,n→∞lim2n+1f(n)=l
∴n→∞lim2nf(n)=n→∞lim2n+1f(n)⋅2=l⋅2,仍為一常數
∴f(n)∈O(2n),成立
由(1),(2),得證f(n)∈O(2n)⟺f(n)∈O(2n+1)
d.
f(n)∈O(n!)⟺f(n)∈O((n+1)!)
(1).prooff(n)∈O(n!)⟹f(n)∈O((n+1)!)
∵f(n)∈O(n!)
∴∃k≥0,n→∞limn!f(n)=k
∴n→∞lim(n+1)!f(n)=n→∞limn!f(n)⋅n+11=n→∞limk⋅n+11=0,仍為一常數
∴f(n)∈O(n!)
(2).prooff(n)∈O(n!)⟸f(n)∈O((n+1)!)
∵f(n)∈O((n+1)!)
∴∃k≥0,n→∞lim(n+1)!f(n)=l
∴n→∞limn!f(n)=n→∞lim(n+1)!f(n)⋅(n+1)=n→∞liml⋅(n+1)=∞,無法收斂成一常數
假設命題成立,設f(n)=(n+1)!,則
n→∞limn!f(n)=n→∞limn!(n+1)!=n→∞limn+1=∞
此處產生矛盾,故f(n)∈O(n!)⟸f(n)∈O((n+1)!)不成立,故原命題不成立。
∴f(n)∈O(n!)
由(1),(2),得證f(n)∈O(n!)⟺f(n)∈O((n+1)!)
上次沒證明出來的第四題
題目:序列開始時只包含一個正整數 n,接著每次對此序列進行如下操作:在序
列中找到任意一個大於 1 的正整數 k,接著把此數換成任意兩個正整數 a,b,其中a+b=k,則此操作得 a×b 分,且數列會多出一項。重複進行以上操作,直到序列中的數均為 1 為止。試證:所有操作的得分總和為2n2−n
假設命題成立,
n+1=(i)+(n−i+1),此步驟得i(n−i+1)=ni−i2+i分
i得分為:2i2−i,n−i+1得分為2(n−i+1)2−(n−i+1)
將三步驟的分數相加:ni−i2+i+2i2−i+2(n−i+1)2−(n−i+1)=2n2+n,成立
故命題成立。